{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Root of N-Ary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #tree #depth-first-search #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #树 #深度优先搜索 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findRoot"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到 N 叉树的根节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一棵&nbsp;<a href=\"https://leetcode.cn/explore/learn/card/n-ary-tree/\" target=\"_blank\">N 叉树</a>&nbsp;的所有节点在一个数组&nbsp;&nbsp;<code>Node[] tree</code>&nbsp;中，树中每个节点都有 <strong>唯一的值</strong> 。</p>\n",
    "\n",
    "<p>找到并返回 N 叉树的 <strong>根节点 </strong>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>自定义测试：</strong></p>\n",
    "\n",
    "<p><em>N 叉树的输入序列为其层序遍历序列，每组子节点用 null 分隔（见示例）。</em></p>\n",
    "\n",
    "<p><em><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/07/21/sample_4_964.png\" style=\"width:300px\" /></em></p>\n",
    "\n",
    "<p>上图中的 N 叉树的序列化描述为 <code>[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]</code> 。</p>\n",
    "\n",
    "<p><strong>测试将以下列方式进行：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>输入数据的形式为树的序列化描述。</li>\n",
    "\t<li>驱动程序代码将根据序列化的输入数据构造树，并以任意顺序将每个 <code>Node</code> 对象放入一个数组中。</li>\n",
    "\t<li>驱动程序代码将把数组传递给 <code>findRoot</code> ，你所编写的函数应该在数组中查找并返回根 <code>Node</code> 对象。</li>\n",
    "\t<li>驱动程序代码将接受返回的 <code>Node</code> 对象并对其进行序列化。如果序列化的结果和输入数据 <strong>相同</strong> ，则测试 <strong>通过</strong> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2018/10/12/narytreeexample.png\" style=\"width:250px\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>tree = [1,null,3,2,4,null,5,6]\n",
    "<strong>输出：</strong>[1,null,3,2,4,null,5,6]\n",
    "<strong>解释：</strong>来自输入数据的树如上所示。\n",
    "驱动程序代码创建树，并以任意顺序向 findRoot 提供 Node 对象。\n",
    "例如，传递的数组可以是 [Node(5),Node(4),Node(3),Node(6),Node(2),Node(1)] 或 [Node(2),Node(6),Node(1),Node(3),Node(5),Node(4)] 。\n",
    "findRoot 函数应该返回根 Node(1) ，驱动程序代码将序列化它并与输入数据进行比较。\n",
    "输入数据和序列化的 Node(1) 相同，因此测试通过。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/11/08/sample_4_964.png\" style=\"height:241px; width:296px\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>tree = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]\n",
    "<strong>输出：</strong>[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>节点的总个数在&nbsp;<code>[1,&nbsp;5*10^4]</code>&nbsp;之间。</li>\n",
    "\t<li>每个节点都有唯一的值。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>你可以使用 O(1) 额外内存空间且 O(n) 时间复杂度的算法来找到该树的根节点吗？</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-root-of-n-ary-tree](https://leetcode.cn/problems/find-root-of-n-ary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-root-of-n-ary-tree](https://leetcode.cn/problems/find-root-of-n-ary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,null,3,2,4,null,5,6]', '[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val, parent = None):\n",
    "        self.val = val\n",
    "        self.parent = parent\n",
    "\n",
    "class Solution:\n",
    "    def add(self, val):\n",
    "\n",
    "        self.nodes[val] = Node(val)\n",
    "\n",
    "        return\n",
    "\n",
    "    def findRoot(self, node):\n",
    "        if not node.parent:\n",
    "            return node\n",
    "\n",
    "        root = node\n",
    "        while root.parent:\n",
    "            root = root.parent\n",
    "\n",
    "        while node != root:\n",
    "            tmp = node.parent\n",
    "            node.parent = root\n",
    "            node = tmp\n",
    "\n",
    "        return root\n",
    "\n",
    "    def merge(self, A, B, remove_list):\n",
    "        root_A = self.findRoot(A)\n",
    "        root_B = self.findRoot(B)\n",
    "\n",
    "        if root_A == root_B:\n",
    "            remove_list.append([A.val, B.val])\n",
    "            return \n",
    "\n",
    "        root_A.parent = root_B\n",
    "        \n",
    "\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        self.nodes = dict()\n",
    "        \n",
    "        res = []\n",
    "        for val_A, val_B in edges:\n",
    "            if val_A not in self.nodes:\n",
    "                self.add(val_A)\n",
    "            \n",
    "            if val_B not in self.nodes:\n",
    "                self.add(val_B)\n",
    "\n",
    "            A = self.nodes[val_A]\n",
    "            B = self.nodes[val_B]\n",
    "            self.merge(A, B, res)\n",
    "\n",
    "        return res[-1] if res else res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val, parent = None):\n",
    "        self.val = val\n",
    "        self.parent = parent\n",
    "\n",
    "class Solution:\n",
    "    def add(self, val):\n",
    "\n",
    "        self.nodes[val] = Node(val)\n",
    "\n",
    "        return\n",
    "\n",
    "    def findRoot(self, node):\n",
    "        if not node.parent:\n",
    "            return node\n",
    "\n",
    "        root = node\n",
    "        while root.parent:\n",
    "            root = root.parent\n",
    "\n",
    "        while node != root:\n",
    "            tmp = node.parent\n",
    "            node.parent = root\n",
    "            node = tmp\n",
    "\n",
    "        return root\n",
    "\n",
    "    def merge(self, A, B, remove_list):\n",
    "        root_A = self.findRoot(A)\n",
    "        root_B = self.findRoot(B)\n",
    "\n",
    "        if root_A == root_B:\n",
    "            remove_list.append([A.val, B.val])\n",
    "            return \n",
    "\n",
    "        root_A.parent = root_B\n",
    "        \n",
    "\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        self.nodes = dict()\n",
    "        \n",
    "        res = []\n",
    "        for val_A, val_B in edges:\n",
    "            if val_A not in self.nodes:\n",
    "                self.add(val_A)\n",
    "            \n",
    "            if val_B not in self.nodes:\n",
    "                self.add(val_B)\n",
    "\n",
    "            A = self.nodes[val_A]\n",
    "            B = self.nodes[val_B]\n",
    "            self.merge(A, B, res)\n",
    "\n",
    "        return res[-1] if res else res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val, parent = None):\n",
    "        self.val = val\n",
    "        self.parent = parent\n",
    "\n",
    "class Solution:\n",
    "    def add(self, val):\n",
    "\n",
    "        self.nodes[val] = Node(val)\n",
    "\n",
    "        return\n",
    "\n",
    "    def findRoot(self, node):\n",
    "        if not node.parent:\n",
    "            return node\n",
    "\n",
    "        root = node\n",
    "        while root.parent:\n",
    "            root = root.parent\n",
    "\n",
    "        while node != root:\n",
    "            tmp = node.parent\n",
    "            node.parent = root\n",
    "            node = tmp\n",
    "\n",
    "        return root\n",
    "\n",
    "    def merge(self, A, B, remove_list):\n",
    "        root_A = self.findRoot(A)\n",
    "        root_B = self.findRoot(B)\n",
    "\n",
    "        if root_A == root_B:\n",
    "            remove_list.append([A.val, B.val])\n",
    "            return \n",
    "\n",
    "        root_A.parent = root_B\n",
    "        \n",
    "\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        self.nodes = dict()\n",
    "        \n",
    "        res = []\n",
    "        for val_A, val_B in edges:\n",
    "            if val_A not in self.nodes:\n",
    "                self.add(val_A)\n",
    "            \n",
    "            if val_B not in self.nodes:\n",
    "                self.add(val_B)\n",
    "\n",
    "            A = self.nodes[val_A]\n",
    "            B = self.nodes[val_B]\n",
    "            self.merge(A, B, res)\n",
    "\n",
    "        return res[-1] if res else res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        root = []\n",
    "        self.findRoot(t1, t2, root)\n",
    "\n",
    "        if root:\n",
    "            for r in root:\n",
    "                flag = self.identicalTree(r, t2)\n",
    "                if flag == True:\n",
    "                    return True\n",
    "            return False \n",
    "        else:\n",
    "            return False \n",
    "\n",
    "    def findRoot(self, t1, t2, root: List) -> None:\n",
    "        if t1 is None:\n",
    "            return \n",
    "\n",
    "        if t1.val == t2.val:\n",
    "            root.append(t1)\n",
    "\n",
    "        self.findRoot(t1.left, t2, root)\n",
    "        self.findRoot(t1.right, t2, root)\n",
    "\n",
    "    def identicalTree(self, t1, t2) -> bool:\n",
    "        if t1 is None and t2:\n",
    "            return False\n",
    "        elif t2 is None and t1:\n",
    "            return False\n",
    "        elif t1 is None and t2 is None:\n",
    "            return True \n",
    "        \n",
    "        # print(t1, t2)\n",
    "        if t1.val != t2.val:\n",
    "            return False \n",
    "        else:\n",
    "            left_id = self.identicalTree(t1.left, t2.left)\n",
    "            right_id = self.identicalTree(t1.right, t2.right)\n",
    "            if left_id and right_id:\n",
    "                return True \n",
    "            else:\n",
    "                return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:\n",
    "        root = []\n",
    "        self.findRoot(t1, t2, root)\n",
    "\n",
    "        if root:\n",
    "            for r in root:\n",
    "                flag = self.identicalTree(r, t2)\n",
    "                if flag == True:\n",
    "                    return True\n",
    "            return False \n",
    "        else:\n",
    "            return False \n",
    "\n",
    "    def findRoot(self, t1, t2, root: List) -> None:\n",
    "        if t1 is None:\n",
    "            return \n",
    "\n",
    "        if t1.val == t2.val:\n",
    "            root.append(t1)\n",
    "\n",
    "        self.findRoot(t1.left, t2, root)\n",
    "        self.findRoot(t1.right, t2, root)\n",
    "\n",
    "    def identicalTree(self, t1, t2) -> bool:\n",
    "        if t1 is None and t2:\n",
    "            return False\n",
    "        elif t2 is None and t1:\n",
    "            return False\n",
    "        elif t1 is None and t2 is None:\n",
    "            return True \n",
    "        \n",
    "        # print(t1, t2)\n",
    "        if t1.val != t2.val:\n",
    "            return False \n",
    "        else:\n",
    "            left_id = self.identicalTree(t1.left, t2.left)\n",
    "            right_id = self.identicalTree(t1.right, t2.right)\n",
    "            if left_id and right_id:\n",
    "                return True \n",
    "            else:\n",
    "                return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        value_sum = 0\n",
    "\n",
    "        for node in tree:\n",
    "            value_sum += node.val\n",
    "            for child_node in node.children:\n",
    "                value_sum -= child_node.val\n",
    "\n",
    "        for node in tree:\n",
    "            if value_sum == node.val:\n",
    "                return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        valuesum = 0\n",
    "        for node in tree:\n",
    "            valuesum += node.val\n",
    "            for nxt in node.children:\n",
    "                valuesum -= nxt.val\n",
    "        \n",
    "        for node in tree:\n",
    "            if node.val == valuesum:\n",
    "                return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        xorsum = 0\n",
    "        \n",
    "        for node in tree:\n",
    "            xorsum ^= node.val\n",
    "            for child in node.children:\n",
    "                xorsum ^= child.val\n",
    "            \n",
    "        for node in tree:\n",
    "            if node.val == xorsum:\n",
    "                return node\n",
    "        \n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        root = 0\n",
    "\n",
    "        for node in tree:\n",
    "            root ^= node.val\n",
    "            for chlid in node.children:\n",
    "                root ^= chlid.val\n",
    "        for node in tree:\n",
    "            if node.val == root:\n",
    "                return node\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        total = 0 \n",
    "        for node in tree:\n",
    "            if not node: continue\n",
    "            total += node.val\n",
    "            for c in node.children:\n",
    "                total -= c.val\n",
    "        \n",
    "        print(total)\n",
    "        for node in tree:\n",
    "            if not node: continue\n",
    "            if node.val == total:\n",
    "                return node\n",
    "        \n",
    "        return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\"\"\"\n",
    "# 节点的定义。\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        value_sum = 0\n",
    "\n",
    "        for node in tree:\n",
    "            # 该值作为父节点添加\n",
    "            value_sum += node.val\n",
    "            for child in node.children:\n",
    "                # 该值将作为子节点扣除\n",
    "                value_sum -= child.val\n",
    "\n",
    "        #  根节点的值是 valueSum\n",
    "        for node in tree:\n",
    "            if node.val == value_sum:\n",
    "                return node\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        xorsum = 0\n",
    "        for node in tree:\n",
    "            xorsum ^= node.val\n",
    "            for ch in node.children:\n",
    "                xorsum ^= ch.val\n",
    "\n",
    "        for node in tree:\n",
    "            if node.val == xorsum:\n",
    "                return node\n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        node_val = 0\n",
    "        # every node except for root will be visited twice\n",
    "        for node in tree:\n",
    "            node_val += node.val\n",
    "            for c in node.children:\n",
    "                node_val -= c.val\n",
    "        \n",
    "        for node in tree:\n",
    "            if node.val == node_val:\n",
    "                return node\n",
    "        return None\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        valSum = 0\n",
    "        for node in tree:\n",
    "            valSum += node.val\n",
    "            for child in node.children:\n",
    "                valSum -= child.val\n",
    "        \n",
    "        for node in tree:\n",
    "            if node.val == valSum:\n",
    "                return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        # seen = set()\n",
    "        # for node in tree:\n",
    "        #     for chd in node.children:\n",
    "        #         seen.add(chd.val)\n",
    "        # for node in tree:\n",
    "        #     if node.val not in seen:\n",
    "        #         return node\n",
    "\n",
    "        val_sum = 0\n",
    "        for node in tree:\n",
    "            val_sum += node.val\n",
    "            for chd in node.children:\n",
    "                val_sum -= chd.val\n",
    "        for node in tree:\n",
    "            if node.val == val_sum:\n",
    "                return node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        # 官方：遍历所有节点及其子节点，则除根节点外其余节点均出现两次\n",
    "        rootVal = 0\n",
    "        for node in tree:\n",
    "            rootVal += node.val\n",
    "            for n in node.children:\n",
    "                rootVal -= n.val\n",
    "        for node in tree:\n",
    "            if node.val == rootVal:\n",
    "                return node\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        value_sum = 0\n",
    "\n",
    "        for node in tree:\n",
    "            value_sum += node.val \n",
    "            for child in node.children:\n",
    "                value_sum -= child.val \n",
    "        \n",
    "        for node in tree:\n",
    "            if node.val == value_sum:\n",
    "                return node\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        xorsum = 0\n",
    "        for node in tree:\n",
    "            xorsum ^= node.val\n",
    "            for ch in node.children:\n",
    "                xorsum ^= ch.val\n",
    "\n",
    "        for node in tree:\n",
    "            if node.val == xorsum:\n",
    "                return node\n",
    "            for ch in node.children:\n",
    "                if ch.val == xorsum:\n",
    "                    return ch\n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        node_val = 0\n",
    "        # every node except for root will be visited twice\n",
    "        for node in tree:\n",
    "            node_val ^= node.val\n",
    "            for c in node.children:\n",
    "                node_val ^= c.val\n",
    "        \n",
    "        for node in tree:\n",
    "            if node.val == node_val:\n",
    "                return node\n",
    "        return None\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        value = 0\n",
    "\n",
    "        for node in tree:\n",
    "            value ^= node.val\n",
    "            for child in node.children:\n",
    "                value ^= child.val\n",
    "\n",
    "        for node in tree:\n",
    "            if node.val == value:\n",
    "                return node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\"\"\"\n",
    "# 节点的定义。\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        value = 0\n",
    "\n",
    "        for node in tree:\n",
    "            # 该值作为父节点添加\n",
    "            value ^= node.val\n",
    "            for child in node.children:\n",
    "                # 该值将作为子节点扣除\n",
    "                value ^= child.val\n",
    "\n",
    "        #  根节点的值是 valueSum\n",
    "        for node in tree:\n",
    "            if node.val == value:\n",
    "                return node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        value_sum = 0\n",
    "\n",
    "        for node in tree:\n",
    "            value_sum += node.val\n",
    "            for child in node.children:\n",
    "                value_sum -= child.val\n",
    "\n",
    "        for node in tree:\n",
    "            if node.val == value_sum:\n",
    "                return node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        # solution 1: hashset brute force \n",
    "        # all_nodes = set(tree)\n",
    "\n",
    "        # for node in tree:\n",
    "        #     if node.children is not None:\n",
    "        #         for c in node.children:\n",
    "        #             all_nodes.remove(c)\n",
    "        \n",
    "        # if not all_nodes:\n",
    "        #     return None\n",
    "        \n",
    "        # return list(all_nodes)[0]\n",
    "\n",
    "\n",
    "\n",
    "        # solution 2: unique value -> sum\n",
    "\n",
    "        total_sum = 0\n",
    "        for node in tree:\n",
    "            total_sum += node.val\n",
    "            if node.children is not None:\n",
    "                for c in node.children:\n",
    "                    total_sum -= c.val\n",
    "        \n",
    "        for n in tree:\n",
    "            if n.val == total_sum:\n",
    "                return n\n",
    "        \n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        value_sum = 0\n",
    "\n",
    "        for node in tree:\n",
    "            # 该值作为父节点添加\n",
    "            value_sum += node.val\n",
    "            for child in node.children:\n",
    "                # 该值将作为子节点扣除\n",
    "                value_sum -= child.val\n",
    "\n",
    "        #  根节点的值是 valueSum\n",
    "        for node in tree:\n",
    "            if node.val == value_sum:\n",
    "                return node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        hs = {}\n",
    "        for t in tree:\n",
    "            hs[t.val] = t\n",
    "        \n",
    "        for t in tree:\n",
    "            for c in t.children:\n",
    "                if c.val in hs:\n",
    "                    del hs[c.val]\n",
    "                if len(hs) == 1:\n",
    "                    for k,v in hs.items():\n",
    "                        return v\n",
    "\n",
    "        for k,v in hs.items():\n",
    "            return v\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        counter = defaultdict(int)\n",
    "        for node in tree:\n",
    "            for child in node.children:\n",
    "                counter[child] += 1\n",
    "        for node in tree:\n",
    "            if node not in counter:\n",
    "                return node\n",
    "        return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        record = collections.defaultdict(list)\n",
    "        for node in tree:\n",
    "            for nxt in node.children:\n",
    "                record[nxt] = 1\n",
    "        \n",
    "        for node in tree:\n",
    "            if node not in record:\n",
    "                return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        node_set = set()  ## 包含所有子节点\n",
    "        # 将所有子节点添加到集合中\n",
    "        for node in tree:\n",
    "            for child in node.children:\n",
    "                # 添加值或者节点本身\n",
    "                node_set.add(child.val)\n",
    "        # 查找不在子节点集中的节点，则为根节点\n",
    "        for node in tree:\n",
    "            if node.val not in node_set:\n",
    "                return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        mapping = {}\n",
    "\n",
    "        for node in tree:\n",
    "            for chlid in node.children:\n",
    "                mapping[chlid] = node\n",
    "        for node in tree:\n",
    "            if node not in mapping:\n",
    "                return node\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        child_dict = {node.val: 0 for node in tree}\n",
    "        for i in range(len(tree)):\n",
    "            for child in tree[i].children:\n",
    "                child_dict[child.val] = 1\n",
    "        for i in range(len(tree)):\n",
    "            if child_dict[tree[i].val] == 0:\n",
    "                return tree[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        child_dict = {node.val: 0 for node in tree}\n",
    "        for i in range(len(tree)):\n",
    "            for child in tree[i].children:\n",
    "                child_dict[child.val] = 1\n",
    "        for i in range(len(tree)):\n",
    "            if child_dict[tree[i].val] == 0:\n",
    "                return tree[i]\n",
    "\n",
    "        # # 包含所有子节点\n",
    "        # seen = set()\n",
    "\n",
    "        # # 将所有子节点添加到集合中\n",
    "        # for node in tree:\n",
    "        #     for child in node.children:\n",
    "        #         # 我们可以添加值或者节点本身\n",
    "        #         seen.add(child.val)\n",
    "\n",
    "        # # 查找不在子节点集中的节点\n",
    "        # for node in tree:\n",
    "        #     if node.val not in seen:\n",
    "        #         return node\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        a = set()\n",
    "        for node in tree:\n",
    "            if node not in a:\n",
    "                for child in node.children:\n",
    "                    a.add(child.val)\n",
    "        for node in tree:\n",
    "            if node.val not in a:\n",
    "                return node\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        s = set()\n",
    "        for node in tree:\n",
    "            for c in node.children:\n",
    "                s.add(c.val)\n",
    "        \n",
    "        for node in tree:\n",
    "            if node.val not in s:\n",
    "                return node\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        #### 看有没有父亲\n",
    "        has_parent = set()\n",
    "        for x in tree:\n",
    "            for y in x.children:\n",
    "                has_parent.add(y)\n",
    "        for x in tree:\n",
    "            if x not in has_parent:\n",
    "                return x\n",
    "                \n",
    "    def findRoot2(self, tree: List['Node']) -> 'Node':\n",
    "        #### 看有没有入\n",
    "        has_in = set()\n",
    "        for x in tree:\n",
    "            for y in x.children:\n",
    "                has_in.add(y)\n",
    "        for x in tree:\n",
    "            if x not in has_in:\n",
    "                return x\n",
    "                \n",
    "    def findRoot3(self, tree: List['Node']) -> 'Node':\n",
    "        #### 异或\n",
    "        xornum = 0\n",
    "        for x in tree:\n",
    "            xornum ^= x.val\n",
    "            for y in x.children:\n",
    "                xornum ^= y.val\n",
    "\n",
    "        for x in tree:\n",
    "            if x.val == xornum:\n",
    "                return x\n",
    "                \n",
    "    def findRoot4(self, tree: List['Node']) -> 'Node':\n",
    "        node_depth = defaultdict(int)   #结点--深度\n",
    "\n",
    "        #### 求结点的深度\n",
    "        def get_depth(x : 'Node') -> int:\n",
    "            if x in node_depth:\n",
    "                return node_depth[x]\n",
    "            if len(x.children) == 0:\n",
    "                node_depth[x] = 1\n",
    "                return 1\n",
    "            max_dep = max([get_depth(y) for y in x.children])\n",
    "            node_depth[x] = max_dep + 1\n",
    "            return max_dep + 1\n",
    "\n",
    "        for x in tree:\n",
    "            get_depth(x)\n",
    "\n",
    "        #### 最大深度\n",
    "        max_dep = -1\n",
    "        res = None\n",
    "        for node, dep in node_depth.items():\n",
    "            if dep > max_dep:\n",
    "                max_dep = dep\n",
    "                res = node\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        visited = set()\n",
    "        for node in tree:\n",
    "            for child in node.children:\n",
    "                visited.add(child.val)\n",
    "        \n",
    "        for node in tree:\n",
    "            if node.val not in visited:\n",
    "                return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        seen = set()\n",
    "        for t in tree:\n",
    "            for c in t.children:\n",
    "                seen.add(c.val)\n",
    "        \n",
    "        for t in tree:\n",
    "            if t.val not in seen:\n",
    "                return t\n",
    "\n",
    "        return -1\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        # child_dict = {node.val: 0 for node in tree}\n",
    "        # for i in range(len(tree)):\n",
    "        #     for child in tree[i].children:\n",
    "        #         child_dict[child.val] = 1\n",
    "        # for i in range(len(tree)):\n",
    "        #     if child_dict[tree[i].val] == 0:\n",
    "        #         return tree[i]\n",
    "\n",
    "        # 包含所有子节点\n",
    "        seen = set()\n",
    "\n",
    "        # 将所有子节点添加到集合中\n",
    "        for node in tree:\n",
    "            for child in node.children:\n",
    "                # 我们可以添加值或者节点本身\n",
    "                seen.add(child.val)\n",
    "\n",
    "        # 查找不在子节点集中的节点\n",
    "        for node in tree:\n",
    "            if node.val not in seen:\n",
    "                return node\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        '''\n",
    "        mp = {}\n",
    "        visited = set([node.val for node in tree])\n",
    "\n",
    "        for node in tree:\n",
    "            mp[node.val] = node\n",
    "            for e in node.children:\n",
    "                visited.remove(e.val)\n",
    "        return mp[list(visited)[0]]\n",
    "        '''\n",
    "\n",
    "        visited = set()\n",
    "        for node in tree:\n",
    "            for child in node.children:\n",
    "                visited.add(child.val)\n",
    "        for node in tree:\n",
    "            if node.val not in visited:\n",
    "                return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        mp = {}\n",
    "        visited = set([node.val for node in tree])\n",
    "\n",
    "        for node in tree:\n",
    "            mp[node.val] = node\n",
    "            for e in node.children:\n",
    "                visited.remove(e.val)\n",
    "        return mp[list(visited)[0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\"\"\"\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        # 包含所有子节点\n",
    "        seen = set()\n",
    "\n",
    "        # 将所有子节点添加到集合中\n",
    "        for node in tree:\n",
    "            for child in node.children:\n",
    "                # 我们可以添加值或者节点本身\n",
    "                seen.add(child.val)\n",
    "\n",
    "        # 查找不在子节点集中的节点\n",
    "        for node in tree:\n",
    "            if node.val not in seen:\n",
    "                return node\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        has_parent = set()\n",
    "        for x in tree:\n",
    "            for y in x.children:\n",
    "                has_parent.add(y)\n",
    "        for x in tree:\n",
    "            if x not in has_parent:\n",
    "                return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        has_parent = set()\n",
    "        for x in tree:\n",
    "            for y in x.children:\n",
    "                has_parent.add(y)\n",
    "        for x in tree:\n",
    "            if x not in has_parent:\n",
    "                return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        # 包含所有子节点\n",
    "        seen = set()\n",
    "\n",
    "        # 将所有子节点添加到集合中\n",
    "        for node in tree:\n",
    "            for child in node.children:\n",
    "                # 我们可以添加值或者节点本身\n",
    "                seen.add(child.val)\n",
    "\n",
    "        # 查找不在子节点集中的节点\n",
    "        for node in tree:\n",
    "            if node.val not in seen:\n",
    "                return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        ans = set()\n",
    "\n",
    "        for node in tree:\n",
    "            for child in node.children:\n",
    "                ans.add(child)\n",
    "\n",
    "        for node in tree:\n",
    "            if node not in ans:\n",
    "                return node\n",
    "        \n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        # solution 1: hashset brute force \n",
    "        all_nodes = set(tree)\n",
    "\n",
    "        for node in tree:\n",
    "            if node.children is not None:\n",
    "                for c in node.children:\n",
    "                    all_nodes.remove(c)\n",
    "        \n",
    "        if not all_nodes:\n",
    "            return None\n",
    "        \n",
    "        return list(all_nodes)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        seen = set()\n",
    "        for node in tree:\n",
    "            for child in node.children:\n",
    "                seen.add(child.val)\n",
    "        \n",
    "        for node in tree:\n",
    "            if node.val not in seen:\n",
    "                return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        parents = set()\n",
    "        children = set()\n",
    "\n",
    "        for node in tree:\n",
    "            parents.add(node)\n",
    "            for child in node.children:\n",
    "                children.add(child)\n",
    "\n",
    "        return (parents - children).pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        self.deepStat = {}\n",
    "        root = None\n",
    "        maxDeep = -1\n",
    "        for node in tree:\n",
    "            deep = self.getDeep(node)\n",
    "            if deep > maxDeep:\n",
    "                root = node\n",
    "                maxDeep = deep\n",
    "        return root\n",
    "\n",
    "    def getDeep(self, node):\n",
    "        if not node.children:\n",
    "            return 1\n",
    "        if node in self.deepStat:\n",
    "            return self.deepStat[node]\n",
    "        deep = -1\n",
    "        for child in node.children:\n",
    "            deep = max(deep, self.getDeep(child))\n",
    "        deep += 1\n",
    "        self.deepStat[node] = deep\n",
    "        return deep"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRoot(self, tree: List['Node']) -> 'Node':\n",
    "        self.deepStat = {}\n",
    "        root = None\n",
    "        maxDeep = -1\n",
    "        for node in tree:\n",
    "            deep = self.getDeep(node)\n",
    "            if deep > maxDeep:\n",
    "                root = node\n",
    "                maxDeep = deep\n",
    "        return root\n",
    "\n",
    "    def getDeep(self, node):\n",
    "        if node in self.deepStat:\n",
    "            return self.deepStat[node]\n",
    "        if not node.children:\n",
    "            self.deepStat[node] = 1\n",
    "            return 1\n",
    "        deep = -1\n",
    "        for child in node.children:\n",
    "            deep = max(deep, self.getDeep(child))\n",
    "        deep += 1\n",
    "        self.deepStat[node] = deep\n",
    "        return deep"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
